package com.example.binarytree;

/**
 * @author Jonathan
 * 2021/4/16 21:47
 * 另外一种解法，讲每一个节点的父节点关系存在hashmap里面
 */
public class LowestCommonAncestor {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public static class Info {
        public TreeNode ans;
        public boolean findO1;
        public boolean findO2;

        public Info(TreeNode ans, boolean findO1, boolean findO2) {
            this.ans = ans;
            this.findO1 = findO1;
            this.findO2 = findO2;
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return process(root, p, q).ans;
    }

    public Info process(TreeNode x, TreeNode o1, TreeNode o2) {
        if (x == null) {
            return new Info(null, false, false);
        }
        // 从左边获取信息
        Info left = process(x.left, o1, o2);
        Info right = process(x.right, o1, o2);

        // 构建出信息返给上一层
        boolean findO1 = x == o1 || left.findO1 || right.findO1;
        boolean find02 = x == o2 || left.findO2 || right.findO2;
        // o1 o2 最初的交汇点在那里
        // 1) 提前在左树交汇了
        // 2) 提前在右树交汇了
        // 3) 在当前节点交汇
        // 4) 保持答案为null
        TreeNode ans = null;
        if (left.ans != null) {
            ans = left.ans;
        }
        if (right.ans != null) {
            ans = right.ans;
        }
        if (ans == null) {
            if (findO1 && find02) {
                ans = x;
            }
        }
        return new Info(ans, findO1, find02);
    }
}
